import java.util.HashSet;
import java.util.Set;

/**
 * 判断一个链表上是否有环。
 * 通过双指针追赶，如果说一个链表有环，那么跑得快点，在N次循环中，终究会遇到跑得慢的。
 * 所以说，如果遇到了，就证明有环。
 */
public class JavaDemo8 {
    public static void main(String[] args) {
        int[] arrays = {1, 2, 2, 3, 3,4, 4, 5, 5};
        ListNode head = new ListNode(arrays[0]);
        ListNode next = head;

        for (int i = 1; i < arrays.length; i++) {
           ListNode  node = new ListNode(arrays[i]);
            next.next = node;
            next = node;
        }
        // 在这里。我们最后的节点设置为首节点。
       next.next=head;
        System.out.println( haveLoop(head));
    }

    private static boolean haveLoop(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if (fast==slow){
                return true;
            }
        }
        return false;
    }



}
